題目:

Given a string s, find the length of the longest substring without repeating characters.

給定一個字串,回傳其中最大的無重複字元字串長度

我們的第二題medium,題目簡單暴力,我一開始沒什麼頭緒,腦中滿滿的超時暴力解,直到在related topics中看到sliding window這個陌生的字眼
上網搜尋了一下,發現原來是所謂的「滑動窗口演算法」,深入了解後,對這題也開始有了頭緒

那我們簡單講一下滑動窗口演算法(sliding window)是什麼:
這個演算法主要用在list資料的處理上,要實作我們需要兩個指標儲存index分別代表窗口的兩側,而兩個指標中間便是我們要操作的窗口
透過指標的移動,我們就能變更窗口的大小及涵蓋內容,至於它會怎樣提高我們程式效率,我這邊舉個例來說明:

給一個list[1,2,3,4,5]然後我們要找出所有連續三數的合,最直接的解法就是取 index 0,1,2相加,1,2,3相加......
而使用sliding window的話,我們先宣兩個指標(start->s表示,end->e表示),讓它們都在index 0開始[1(s)(e),2,3,4,5],接著讓e開始往後移,一邊把e位置的值加到sum,我們可以透過s,e的距離來推算當前窗口的大小
當窗口大小達到3[1(s),2,3(e),4,5],我們便可以記錄當前的sum,接著繼續移動e,會導致窗口>3,於是我們將s值往前移,將窗口大小重新降為3,同時sum減掉s離開位置的值[1,2(s),3,4(e),5],此時sum又是另一個連續三數合
我們持續如此記錄值到e到達陣列最尾端,我們便取得所有連續三數合

法一跟法二差在前者重複取值計算,而後者透過前端尾端的加減重複利用了中間的值,一旦資料變得巨大,兩者的效率差就會更為明顯

有了這種思考模式,我成功構築出我的程式

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        s1=set()
        ans=0
        start=0
        end=0
        
        while True:
            if end>len(s)-1:
                return ans
                
            if s[end] in s1:
                if len(s1)>ans:
                    ans=len(s1)
                s1.remove(s[start])
                start=start+1
                
            if s[end] not in s1:
                s1.add(s[end])
                if end==(len(s)-1):
                    if len(s1)>ans:
                        ans=len(s1)   
                end=end+1

我這邊用了類似1.法二的模式結合sliding window
一邊移動窗口一邊將路過的字元紀錄到set內
end所在位置的值如果不在set內就紀錄後end繼續往前
在set內end就停止而start要往前移動且在set中remove離開位置的值,在此之前紀錄當下len(set)的值
因為end碰觸到set裡有的值的那刻,len(set)便是最大無重複字元字串長度的其中一種可能(因為到目前為止字元無重複),我們將其記錄
接著start會持續往前持續remove,直到end接觸的值不在set內,end再繼續前進紀錄,重複模式,直到尾端
過程中紀錄到最大的len(set)就是最大無重複字元字串長度,也是我們要回傳的值
最後執行時間67ms(faster than 87.71%)

本題學習到的重點:sliding window
那我們下題見